package sort;

public class QuickSort4 {

	public static void main(String[] args) {
		int[] array = { 5, 9, 4, 6, 3, 513, 645, 5, 1, 32, 65, 56, 123312, 465,
				565, -6, -88965, -456, 11, 0, 0, 0, 0};
		quickSort(array, 0, array.length - 1);
		for (int i : array) {
			System.out.print(i + " ");
		}
	}

	public static void quickSort(int[] array, int left, int right) {
		if (array == null || left >= right) {
			return;
		}
		int index = partion(array, left, right);
		quickSort(array, left, index - 1);
		quickSort(array, index + 1, right);
	}

	public static int partion(int[] array, int left, int right) {
		if (left > right) {
			return left;
		}
		int start = left;
		int end = right - 1;
		int key = array[right];
		while (start <= end) {
			while (start <= end && array[end] > key) {
				end--;
			}
			while (start <= end && array[start] <= key) {
				start++;
			}
			if (start < end) {
				MaoPaoSort.swap(array, start, end);
			}
		}
		MaoPaoSort.swap(array, start, right);
		return start;
	}
}
